package cn.corffen.test.algorithm.offer;

import cn.corffen.test.algorithm.RandomListNode;
import cn.corffen.test.algorithm.leetcode.TreeNode;
import cn.corffen.test.algorithm.leetcode.easy.ListNode;

import java.util.*;


public class Solution {
    public static void main(String[] args) {

    }


    /**
     * 3. 数组中重复的数字
     * 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。
     * 数组中某些数字是重复的，但不知道有几个数字是重复的，
     * 也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
     * <p>
     * Input:
     * {2, 3, 1, 0, 2, 5}
     * <p>
     * Output:
     * 2
     */
    public boolean duplicate(int[] nums, int length, int[] duplication) {
        if (nums == null || length <= 0)
            return false;
        for (int i = 0; i < length; i++) {
            while (nums[i] != i) {
                if (nums[i] == nums[nums[i]]) {
                    duplication[0] = nums[i];
                    return true;
                }
                swap(nums, i, nums[i]);
            }
        }
        return false;
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    /**
     * 4. 二维数组中的查找
     * 题目描述
     * 给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。
     * 给定一个数，判断这个数是否在该二维数组中。
     * <p>
     * Consider the following matrix:
     * [
     * [1,   4,  7, 11, 15],
     * [2,   5,  8, 12, 19],
     * [3,   6,  9, 16, 22],
     * [10, 13, 14, 17, 24],
     * [18, 21, 23, 26, 30]
     * ]
     * <p>
     * Given target = 5, return true.
     * Given target = 20, return false.
     * 解题思路
     * 要求时间复杂度 O(M + N)，空间复杂度 O(1)。其中 M 为行数，N 为 列数。
     * <p>
     * 该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间，当前元素的查找区间为左下角的所有元素。
     */
    public boolean Find(int target, int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;
        int r = 0;
        int c = cols - 1;
        while (r <= rows - 1 && c >= 0) {
            if (matrix[r][c] == target) {
                return true;
            } else if (target > matrix[r][c]) {
                r++;
            } else {
                c--;
            }
        }
        return false;
    }

    /**
     * 5.替换空格
     *
     * @param str
     * @return
     */
    public String replaceSpace(StringBuilder str) {
        int p1 = str.length() - 1;
        for (int i = 0; i <= p1; i++) {
            if (str.charAt(i) == ' ') {
                str.append("  ");
            }
        }
        int p2 = str.length() - 1;
        while (p1 >= 0 && p2 > p1) {
            char c = str.charAt(p1--);
            if (c == ' ') {
                str.setCharAt(p2--, '0');
                str.setCharAt(p2--, '2');
                str.setCharAt(p2--, '%');
            } else {
                str.setCharAt(p2--, c);
            }
        }
        return str.toString();
    }

    public String replaceSpace1(StringBuilder str) {

        return str.toString().replaceAll(" ", "%20");
    }

    /**
     * 6. 从尾到头打印链表
     * 题目描述
     * 从尾到头反过来打印出每个结点的值。
     */
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        while (listNode != null) {
            stack.addLast(listNode.val);
            listNode = listNode.next;
        }
        ArrayList<Integer> ans = new ArrayList<>();
        while (!stack.isEmpty()) {
            ans.add(stack.removeLast());
        }
        return ans;
    }


    /**
     * 7. 重构二叉树
     * 利用前序遍历和中序遍历的数组,构造原始的二叉树
     *
     * @param pre
     * @param in
     * @return
     */
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            map.put(in[i], i);
        }
        return helperBinary(pre, 0, pre.length - 1, 0, map);
    }

    public TreeNode helperBinary(int[] pre, int pl, int pr, int il, Map<Integer, Integer> map) {
        if (pl > pr) {
            return null;
        }
        //前序遍历的第一个是根节点
        TreeNode root = new TreeNode(pre[pl]);
        int index = map.get(root.val);
        int leftSize = index - il;
        //pre 左边位置的下一个 右边的结束位置是左边的值+leftSize,中序的起始位置还是il
        root.left = helperBinary(pre, pl + 1, pl + leftSize, il, map);
        //右节点 pre的左边的位置从pl+leftSize+1开始,右边的位置是pr,而中序的起始位置是il+leftSize+1.
        root.right = helperBinary(pre, pl + leftSize + 1, pr, il + leftSize + 1, map);
        return root;
    }

    /**
     * 8.二叉树的下一个节点
     * 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
     * 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
     */
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        //如果当前节点的右节点不为null,那么它的下一个节点就是右节点的最左节点
        if (pNode.right != null) {
            TreeLinkNode node = pNode.right;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        } else {
            //否则就向上回溯其父节点.如果父节点的左节点为当前节点,那么就返回.重复往上回溯父节点
            while (pNode.next != null) {
                TreeLinkNode node = pNode.next;
                //如果父节点的左节点为当前节点,就返回.
                if (node.left == pNode) {
                    return node;
                }
                pNode = pNode.next;
            }
        }
        return null;
    }

    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        if (stack2.isEmpty()) {
            throw new IllegalStateException("queue is empty");
        }
        return stack2.pop();
    }

    /**
     * 10.1 大家都知道斐波那契数列，现在要求输入一个整数n，
     * 请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
     * n<=39
     *
     * @param n
     * @return
     */
    public int Fibonacci(int n) {
        if (n < 2) {
            return n;
        }
        int first = 0;
        int second = 1;
        for (int i = 1; i < n; i++) {
            int temp = first + second;
            first = second;
            second = temp;
        }
        return second;
    }

    /**
     * 10.2 矩形覆盖
     * 我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。
     * 请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，总共有多少种方法？
     * 思路:
     * 要覆盖 2*n 的大矩形，可以先覆盖 2*1 的矩形，
     * 再覆盖 2*(n-1) 的矩形；或者先覆盖 2*2 的矩形，
     * 再覆盖 2*(n-2) 的矩形。而覆盖 2*(n-1) 和 2*(n-2) 的矩形可以看成子问题。
     * 该问题的递推公式如下：
     */
    public int RectCover(int target) {
        if (target <= 2) {
            return target;
        }
        int first = 1;
        int second = 2;

        for (int i = 3; i <= target; i++) {
            int temp = first + second;
            first = second;
            second = temp;
        }
        return second;
    }

    /**
     * 10.3 青蛙跳台阶
     * 一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
     */
    public int JumpFloor(int target) {
        if (target < 1) {
            return -1;
        }
        if (target < 3) {
            return target;
        }
        int first = 1;
        int second = 2;
        for (int i = 3; i <= target; i++) {
            int temp = first + second;
            first = second;
            second = temp;
        }
        return second;
    }

    /**
     * 10.4 变态跳台阶
     * 一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级... 它也可以跳上 n 级。
     * 求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
     * f(n) = f(n-1)+f(n-2)+f(n-3)+...+f(1);
     * f(n-1) =      f(n-2)+f(n-3)+...+f(1);
     * f(n) = 2*f(n-1);
     */
    public int JumpFloorII(int target) {
        if (target < 1) {
            return 0;
        }
        return (int) Math.pow(2, target - 1);
    }

    /**
     * 11. 旋转数组的最小数字
     * 题目描述
     * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
     * 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
     * <p>
     * 使用二分查找和右边的值进行比较.
     * 如果a[mid]>a[hi] 说明在右边. 则lo = mid+1;
     * 如果a[mid] = a[hi] 将hi往左移一个位置 hi = hi-1;
     * 如果a[mid]<a[hi] 说明在左边 将 hi = mid;
     * <p>
     * 循环条件是lo<hi
     * 返回lo
     */
    public int minNumberInRotateArray(int[] nums) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > nums[hi]) {
                lo = mid + 1;
            } else if (nums[mid] == nums[hi]) {
                hi = hi - 1;
            } else {
                hi = mid;
            }
        }
        return nums[lo];
    }

    /**
     * 12. 矩阵中的路径
     * 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
     * 路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
     * 如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
     * 例如 \ a & b & c &e
     * \ s & f & c & s
     * \ a & d & e& e
     * <p>
     * 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，
     * 因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
     *
     * @param matrix
     * @param rows
     * @param cols
     * @param str
     * @return
     */
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        char[][] arr = buildArr(matrix, rows, cols);
        this.rows = rows;
        this.cols = cols;
        boolean[][] marked = new boolean[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (backTrace(arr, 0, i, j, str, marked)) {
                    return true;
                }
            }
        }
        return false;
    }

    private int rows;
    private int cols;
    private int[][] next = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    private boolean backTrace(char[][] arr, int pathLen, int r, int c, char[] str, boolean[][] marked) {
        if (pathLen == str.length) {
            return true;
        }
        if (r >= rows || r < 0 || c < 0 || c >= cols || arr[r][c] != str[pathLen] || marked[r][c]) {
            return false;
        }
        marked[r][c] = true;
        for (int[] i : next) {
            if (backTrace(arr, pathLen + 1, r + i[0], c + i[1], str, marked)) {
                return true;
            }
        }
        marked[r][c] = false;
        return false;
    }

    private char[][] buildArr(char[] matrix, int rows, int cols) {
        char[][] arr = new char[rows][cols];
        for (int i = 0, index = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                arr[i][j] = matrix[index++];
            }
        }
        return arr;
    }

    /**
     * 13. 机器人的运动范围
     * 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，
     * 每一次只能向左，右，上，下四个方向移动一格，
     * 但是不能进入行坐标和列坐标的数位之和大于k的格子。
     * 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
     * 但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
     * <p>
     * 使用深度优先搜索找到从0,0到threshold之间的步数.
     *
     * @param threshold
     * @param rows
     * @param cols
     * @return
     */
    public int movingCount(int threshold, int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
        this.threshold = threshold;
        initDigit();
        boolean[][] marked = new boolean[rows][cols];
        dfs(marked, 0, 0);
        return cnt;
    }

    private void dfs(boolean[][] marked, int r, int c) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || marked[r][c]) {
            return;
        }
        marked[r][c] = true;
        if (digit[r][c] > threshold) {
            return;
        }
        cnt++;
        for (int[] ints : next) {
            dfs(marked, r + ints[0], c + ints[1]);
        }
    }

    private void initDigit() {
        digit = new int[rows][cols];

        int[] digitArr = new int[Math.max(rows, cols)];
        for (int i = 0; i < digitArr.length; i++) {
            int n = i;
            while (n > 0) {
                digitArr[i] += n % 10;
                n /= 10;
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                digit[i][j] = digitArr[i] + digitArr[j];
            }
        }
    }

    private int threshold;
    private int[][] digit;
    private int cnt;

    /**
     * 14.剪绳子
     * 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
     * <p>
     * 示例 1:
     * <p>
     * 输入: 2
     * 输出: 1
     * 解释: 2 = 1 + 1, 1 × 1 = 1。
     * 示例 2:
     * <p>
     * 输入: 10
     * 输出: 36
     * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
     * 说明: 你可以假设 n 不小于 2 且不大于 58。
     * 假设对于任意的i,他的最大拆分乘积为dp[i],存在1<=j<i使得他的最大值为 j*(i-j)或者j*dp[i-j];
     *
     * @param n
     * @return
     */
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = curMax;
        }
        return dp[n];
    }

    /**
     * 对于上述的优化,任意的值都可以拆解为2*(i-2),2*dp[i-2]中的较大值
     * 或者3*(i-3),3*dp[i-3]中的较大值
     * 这两个值的较大值的解
     *
     * @param n
     * @return
     */
    public int integerBreak1(int n) {
        if (n < 4) {
            return n - 1;
        }
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(Math.max(2 * (i - 2), 2 * dp[i - 2]), Math.max(3 * (i - 3), 3 * dp[i - 3]));
        }
        return dp[n];
    }

    /**
     * 15. 二进制中 1 的个数
     * 题目描述
     * 输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。
     * <p>
     * n & (n-1) 可以消除末位的1
     */
    public int NumberOf1(int n) {
//        return Integer.bitCount(n);
        int cnt = 0;
        while (n != 0) {
            cnt++;
            n &= (n - 1);
        }
        return cnt;
    }

    /**
     * 18.1 在 O(1) 时间内删除链表节点
     *
     * @param head
     * @param tobeDelete
     * @return
     */
    public ListNode deleteNode(ListNode head, ListNode tobeDelete) {
        if (head == null || tobeDelete == null) {
            return null;
        }
        //如果待删除的结点的下一个结点不为空,就把下一个结点赋给待删除的结点
        if (tobeDelete.next != null) {
            ListNode cur = tobeDelete.next;
            tobeDelete.val = cur.val;
            tobeDelete.next = cur.next;
        } else {
            //如果待删除的结点是头结点,直接返回null
            if (head == tobeDelete) {
                head = null;
            } else {
                ListNode cur = head;
                //遍历找到current,使其下一个结点指向待删除的结点.
                while (cur.next != tobeDelete) {
                    cur = cur.next;
                }
                //找到把current的下一个结点置空
                cur.next = null;
            }
        }
        return head;
    }

    /**
     * 18.2 删除链表中重复的结点
     * 题目描述
     * 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，
     * 重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
     *
     * @param pHead
     * @return
     */
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return pHead;
        }
        ListNode next = pHead.next;
        if (pHead.val != next.val) {
            pHead.next = deleteDuplication(pHead.next);
            return pHead;
        } else {
            while (next != null && next.val == pHead.val) {
                next = next.next;
            }
            return deleteDuplication(next);
        }
    }

    /**
     * 20. 表示数值的字符串
     * 题目描述
     * 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
     * 例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。
     * 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
     *
     * @param str
     * @return
     */
    public boolean isNumeric(char[] str) {
        if (str == null || str.length == 0)
            return false;
        return new String(str).matches("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?");
    }

    /**
     * 21. 调整数组顺序使奇数位于偶数前面
     *
     * @param array
     */
    public void reOrderArray(int[] array) {
        int n = array.length;
        int[] newArr = new int[n];
        int j = n - 1;
        for (int k = 0, i = 0; k < array.length; k++) {
            if (array[k] % 2 != 0) {
                newArr[i++] = array[k];
            } else {
                newArr[j--] = array[k];
            }
        }
        int lo = j + 1;
        int hi = n - 1;
        while (lo < hi) {
            int temp = newArr[lo];
            newArr[lo] = newArr[hi];
            newArr[hi] = temp;
            lo++;
            hi--;
        }
        System.arraycopy(newArr, 0, array, 0, n);
    }

    /**
     * 题目描述
     * 输入一个链表，输出该链表中倒数第k个结点。
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode p1 = head;
        while (p1 != null && k-- > 0) {
            p1 = p1.next;
        }
        if (k > 0) {
            return null;
        }
        ListNode p2 = head;
        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }

    /**
     * 23.链表中环的入口结点
     * 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
     */
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode fast = pHead;
        ListNode slow = pHead;
        //快慢指针,找到相遇点
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        //如果快指针指向了null,说明是无环
        if (fast.next == null || fast.next.next == null) {
            return null;
        }
        //慢指针从头开始,而快指针从相遇点开始.这两个指针每次走一步
        //那么二者的下一次相遇点一定是环的入口.
        slow = pHead;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 24. 反转链表
     */
    public ListNode ReverseList(ListNode head) {
        ListNode reverse = new ListNode(-1);
        while (head != null) {
            ListNode next = head.next;
            head.next = reverse.next;
            reverse.next = head;
            head = next;
        }
        return reverse.next;
    }

    /**
     * 25. 合并两个排序的链表
     */
    public ListNode Merge(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }

        if (list1 != null) {
            cur.next = list1;
        }
        if (list2 != null) {
            cur.next = list2;
        }
        return head.next;
    }

    /**
     * 26.树的子结构
     * 题目描述
     * 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构
     *
     * @param root1
     * @param root2
     * @return
     */
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }
        return recur(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    }

    public boolean recur(TreeNode root1, TreeNode root2) {
        if (root2 == null) {
            return true;
        }
        if (root1 == null || root1.val != root2.val) {
            return false;
        }
        return recur(root1.left, root2.left) && recur(root1.right, root2.right);
    }


    /**
     * 28. 对称的二叉树
     *
     * @param pRoot
     * @return
     */
    public boolean isSymmetrical(TreeNode pRoot) {
        return check(pRoot, pRoot);
    }

    public boolean check(TreeNode u, TreeNode v) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(u);
        queue.add(v);
        while (!queue.isEmpty()) {
            u = queue.poll();
            v = queue.poll();
            if (u == null && v == null) {
                continue;
            }
            if (u == null || v == null || u.val != v.val) {
                return false;
            }
            queue.add(u.left);
            queue.add(v.right);

            queue.add(u.right);
            queue.add(v.left);
        }
        return true;
    }

    /**
     * 29. 顺时针打印矩阵
     *
     * @param matrix
     * @return
     */
    public ArrayList<Integer> printMatrix(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int r1 = 0;
        int r2 = rows - 1;
        int c1 = 0;
        int c2 = cols - 1;
        ArrayList<Integer> ans = new ArrayList<>();
        while (c1 <= c2 && r1 <= r2) {
            for (int i = c1; i <= c2; i++) {
                ans.add(matrix[c1][i]);
            }
            for (int i = r1 + 1; i <= r2; i++) {
                ans.add(matrix[i][c2]);
            }
            if (r1 != r2) {
                for (int i = c2 - 1; i >= c1; i--) {
                    ans.add(matrix[r2][i]);
                }
            }
            if (c1 != c2) {
                for (int i = r2 - 1; i > r1; i--) {
                    ans.add(matrix[i][c1]);
                }
            }
            c1++;
            c2--;
            r1++;
            r2--;
        }
        return ans;
    }

    /**
     * 31.栈的压入弹出序列
     * 题目描述
     * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
     * 假设压入栈的所有数字均不相等。
     * 例如序列1,2,3,4,5是某栈的压入顺序，
     * 序列4,5,3,2,1是该压栈序列对应的一个弹出序列，
     * 但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
     *
     * @param pushA
     * @param popA
     * @return
     */
    public boolean IsPopOrder(int[] pushA, int[] popA) {
        if (pushA == null || popA == null) {
            return false;
        }
        Stack<Integer> stack = new Stack<>();
        int index = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (!stack.isEmpty() && stack.peek() == popA[index]) {
                index++;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }

    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            ans.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return ans;
    }

    /**
     * 32.2 把二叉树打印成多行
     *
     * @param pRoot
     * @return
     */
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        if (pRoot == null) {
            return ans;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        while (!queue.isEmpty()) {
            ArrayList<Integer> row = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                row.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            ans.add(row);
        }
        return ans;
    }

    /**
     * 32.3 按之字形顺序打印二叉树
     *
     * @param pRoot
     * @return
     */
    public ArrayList<ArrayList<Integer>> Print2(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        if (pRoot == null) {
            return ans;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        boolean reverse = false;
        while (!queue.isEmpty()) {
            ArrayList<Integer> row = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                row.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            if (reverse) {
                Collections.reverse(row);
            }
            reverse = !reverse;
            if (!row.isEmpty()) {
                ans.add(row);
            }
        }
        return ans;
    }

    /**
     * 33.二叉搜索树的后序遍历序列
     * 题目描述
     * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
     * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
     *
     * @param sequence
     * @return
     */
    public boolean VerifySquenceOfBST(int[] sequence) {
        if (sequence == null || sequence.length == 0) {
            return false;
        }
        return verify(sequence, 0, sequence.length - 1);
    }

    public boolean verify(int[] arr, int left, int right) {
        if (left >= right) {
            return true;
        }
        int currentIndex = left;
        int rootVal = arr[right];
        while (currentIndex < right && arr[currentIndex] < rootVal) {
            currentIndex++;
        }
        for (int i = currentIndex; i < right; i++) {
            if (arr[i] < rootVal) {
                return false;
            }
        }
        return verify(arr, left, currentIndex - 1) && verify(arr, currentIndex, right - 1);
    }

    /**
     * 34.二叉树中和为某一值的路径
     * 输入一颗二叉树的根节点和一个整数，
     * 按字典序打印出二叉树中结点值的和为输入整数的所有路径。
     * 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
     *
     * @param root
     * @param target
     * @return
     */

    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    ArrayList<Integer> path = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        if (root == null) {
            return res;
        }
        findPath(root, target, 0);
        return res;
    }

    /**
     * 递归遍历,使用前序遍历
     * 所谓的前序遍历也就是在递归之前做一些数据的处理和条件判断.
     *
     * @param root
     * @param target
     * @param sum
     */
    public void findPath(TreeNode root, int target, int sum) {
        path.add(root.val);
        sum += root.val;
        if (root.left == null && root.right == null && sum == target) {
            res.add(new ArrayList<>(path));
        }
        if (root.left != null) {
            findPath(root.left, target, sum);
        }

        if (root.right != null) {
            findPath(root.right, target, sum);
        }
        //删除最后一个接待
        path.remove(path.size() - 1);
    }

    /**
     * 35. 复杂链表的复制
     *
     * @param pHead
     * @return
     */
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;
        }

        RandomListNode currentNode = pHead;
        //1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
        while (currentNode != null) {
            RandomListNode cloneNode = new RandomListNode(currentNode.label);
            RandomListNode nextNode = currentNode.next;
            currentNode.next = cloneNode;
            cloneNode.next = nextNode;
            currentNode = nextNode;
        }

        currentNode = pHead;
        //2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
        while (currentNode != null) {
            currentNode.next.random = currentNode.random == null ? null : currentNode.random.next;
            currentNode = currentNode.next.next;
        }

        //3、拆分链表，将链表拆分为原链表和复制后的链表
        currentNode = pHead;
        RandomListNode pCloneHead = pHead.next;
        while (currentNode != null) {
            RandomListNode cloneNode = currentNode.next;
            currentNode.next = cloneNode.next;
            cloneNode.next = cloneNode.next == null ? null : cloneNode.next.next;
            currentNode = currentNode.next;
        }

        return pCloneHead;
    }

    private TreeNode pre, head;

    /**
     * 36.将二叉搜索树转成双向链表
     *
     * @param pRootOfTree
     * @return
     */
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        dfs(pRootOfTree);
//        如果是循环双向链表的话,就执行下面的两行代码
//        head.left = pre;
//        pre.right = head;
        return head;
    }

    private void dfs(TreeNode cur) {
        if (cur == null) {
            return;
        }
        dfs(cur.left);
        if (pre != null) {
            pre.right = cur;
        } else {
            head = cur;
        }
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }


    /**
     * 38. 字符串的排列
     * 题目描述
     * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
     * 例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的
     * 所有字符串abc,acb,bac,bca,cab和cba。
     * 输入描述:
     * 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
     *
     * @param str
     * @return
     */
    private ArrayList<String> ans = new ArrayList<>();

    public ArrayList<String> Permutation(String str) {
        if (str == null || str.length() == 0) {
            return ans;
        }
        char[] chars = str.toCharArray();
        backtracking(chars, new boolean[chars.length], new StringBuilder());
        return ans;
    }

    private void backtracking(char[] chars, boolean[] marked, StringBuilder s) {
        if (s.length() == chars.length) {
            ans.add(s.toString());
            return;
        }
        for (int i = 0; i < chars.length; i++) {
            if (marked[i]) {
                continue;
            }
            if (i != 0 && chars[i] == chars[i - 1] && !marked[i - 1]) {
                continue;
            }
            marked[i] = true;
            s.append(chars[i]);
            backtracking(chars, marked, s);
            s.deleteCharAt(s.length() - 1);
            marked[i] = false;
        }
    }


    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> ans = new ArrayList<>();
        if (k < 0 || k > input.length) {
            return ans;
        }
        PriorityQueue<Integer> heapMax = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int i = 0; i < input.length; i++) {
            heapMax.add(input[i]);
            if (heapMax.size() > k) {
                heapMax.poll();
            }
        }
        return new ArrayList<>(heapMax);
    }

    public ArrayList<Integer> topK(int[] input, int k) {
        ArrayList<Integer> ans = new ArrayList<>();
        if (k < 0 || k > input.length) {
            return ans;
        }
        find(input, k - 1);
        for (int i = 0; i < k; i++) {
            ans.add(input[i]);
        }
        return ans;
    }

    private void find(int[] input, int k) {
        int lo = 0;
        int hi = input.length - 1;
        while (lo < hi) {
            int j = partition(input, lo, hi);
            if (j == k) {
                break;
            } else if (j > k) {
                hi = j - 1;
            } else {
                lo = j + 1;
            }
        }
    }

    private int partition(int[] input, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        int v = input[lo];
        while (true) {
            while (i != hi && input[++i] < v) ;
            while (j != lo && input[--j] > v) ;
            if (i >= j) {
                break;
            }
            swapArr(input, i, j);
        }
        swapArr(input, lo, j);
        return j;
    }

    private void swapArr(int[] input, int i, int j) {
        int temp = input[i];
        input[i] = input[j];
        input[j] = temp;
    }

    public int FindGreatestSumOfSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int num : nums) {
            sum = sum <= 0 ? num : sum + num;//如果累加的和sum<0,则从当前项纪录sum
            max = Math.max(max, sum);//记录最后一项的最大值.
        }
        return max;
    }

    /**
     * @param n
     * @return
     */
    public int countDigitOne(int n) {
        int ones = 0;
        for (int m = 1; m < n; m *= 10) {
            int a = n / m;
            int b = n % m;
            ones += (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0);
        }
        return ones;
    }

    /**
     * 44. 数字序列中的某一位数字
     * 题目描述
     * 数字以 0123456789101112131415... 的格式序列化到一个字符串中，求这个字符串的第 index 位。
     *
     * @param index
     * @return
     */
    public int getDigitAtIndex(int index) {
        if (index < 0) {
            return -1;
        }
        if (index < 10) {
            return index;
        }
        int currentIndex = 10;
        int length = 2;
        int bounded = 10;
        while (currentIndex + sumOfLength(length) < index) {
            currentIndex += sumOfLength(length);
            length++;
            bounded *= 10;
        }
        int addNum = (index - currentIndex) / length;
        int curNum = bounded + addNum;
        return Integer.toString(curNum).charAt(index - currentIndex - addNum * length) - '0';
    }

    public int sumOfLength(int length) {
        int count = 9;
        for (int i = 1; i < length; i++) {
            count *= 10;
        }
        return count * length;
    }

    /**
     * @param numbers
     * @return
     */
    public String PrintMinNumber(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            return "";
        }
        int n = numbers.length;
        String[] res = new String[n];
        for (int i = 0; i < n; i++) {
            res[i] = numbers[i] + "";
        }
        Arrays.sort(res, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o1 + o2).compareTo(o2 + o1);
            }
        });
        StringBuilder ans = new StringBuilder();
        for (String re : res) {
            ans.append(re);
        }
        return ans.toString();
    }

    /**
     * 46. 数字翻译成字符串
     *
     * @param s
     * @return
     */
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) == '0' ? 0 : 1;
        for (int i = 2; i <= n; i++) {
            int one = Integer.parseInt(s.substring(i - 1, i));
            if (one != 0) {
                dp[i] += dp[i - 1];
            }
            if (s.charAt(i - 2) == '0') {
                continue;
            }
            int two = Integer.parseInt(s.substring(i - 2, i));
            if (two <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }

    /**
     * 47.礼物的最大值
     * 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。
     * 你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。
     * 给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
     * <p>
     *  
     * <p>
     * 示例 1:
     * <p>
     * 输入:
     * [
     *   [1,3,1],
     *   [1,5,1],
     *   [4,2,1]
     * ]
     * 输出: 12
     * 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
     */
    public int maxValue(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    continue;
                }
                if (i == 0) {
                    grid[i][j] += grid[i][j - 1];
                } else if (j == 0) {
                    grid[i][j] += grid[i - 1][j];
                } else {
                    grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);
                }
            }
        }
        return grid[m - 1][n - 1];
    }

    public int maxValue2(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }

        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j - 1];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[m - 1][n - 1];
    }

    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        int ans = 0;
        int i = -1;
        for (int j = 0; j < s.length(); j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(i, map.get(s.charAt(j)));
            }
            map.put(s.charAt(j), j);
            ans = Math.max(ans, j - i);
        }
        return ans;
    }

    /**
     * 剑指 Offer 51. 数组中的逆序对
     * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
     * 示例 1:
     * <p>
     * 输入: [7,5,6,4]
     * 输出: 5
     *
     * @param nums
     * @return
     */
    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        if (n < 2) {
            return 0;
        }
        int[] copy = new int[n];
        System.arraycopy(nums, 0, copy, 0, n);
        int[] temp = new int[n];
        return reversePairHelper(copy, 0, n - 1, temp);
    }

    private int reversePairHelper(int[] copy, int lo, int hi, int[] temp) {
        if (lo >= hi) {
            return 0;
        }
        int mid = lo + (hi - lo) / 2;
        int leftPairs = reversePairHelper(copy, lo, mid, temp);
        int rightPairs = reversePairHelper(copy, mid + 1, hi, temp);
        if (temp[mid] < temp[mid + 1]) {
            return leftPairs + rightPairs;
        }

        int crossPairs = mergeAndCount(copy, lo, mid, hi, temp);
        return leftPairs + rightPairs + crossPairs;
    }

    private int mergeAndCount(int[] copy, int lo, int mid, int hi, int[] temp) {
        for (int i = lo; i < hi; i++) {
            temp[i] = copy[i];
        }
        int i = lo;
        int j = mid + 1;
        int cnt = 0;
        for (int k = lo; k <= hi; k++) {
            if (i == mid + 1) {
                copy[k] = temp[j++];
            } else if (j == hi + 1) {
                copy[k] = temp[i++];
            } else if (copy[i] <= copy[j]) {
                copy[k] = temp[i++];
            } else {
                copy[k] = temp[j++];
                cnt = mid - i + 1;
            }
        }
        return cnt;
    }

    /**
     * 52.查找两个链表中的第一个公共节点
     * <p>
     * 两个链表都从头开始遍历,当到达末尾时,换向链表继续遍历,当二者相遇时,就是第一个公共结点
     *
     * @param pHead1
     * @param pHead2
     * @return
     */
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode l1 = pHead1;
        ListNode l2 = pHead2;
        while (l1 != l2) {
            l1 = l1 == null ? pHead2 : l1.next;
            l2 = l2 == null ? pHead1 : l2.next;
        }
        return l1;
    }

    /**
     * 53.数字在排序数组中出现的次数
     *
     * @param array
     * @param k
     * @return
     */
    public int GetNumberOfK(int[] array, int k) {
        int first = binarySearch(array, k);
        int end = binarySearch(array, k + 1);
        if (first == array.length || array[first] != k) {
            return 0;
        }
        return end - first;
    }

    public int binarySearch(int[] arr, int k) {
        int lo = 0;
        int hi = arr.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] >= k) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    /**
     * 54.二叉搜索树中第k个节点
     * 中序遍历是有序的.
     *
     * @param pRoot
     * @param k
     * @return
     */
    TreeNode KthNode(TreeNode pRoot, int k) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        int cnt = 0;
        while (pRoot != null || !stack.isEmpty()) {
            while (pRoot != null) {
                stack.push(pRoot);
                pRoot = pRoot.left;
            }
            pRoot = stack.pop();
            if (++cnt == k) {
                return pRoot;
            }
            pRoot = pRoot.right;
        }
        return null;
    }

    private boolean isBalanced = true;

    /**
     * 判断是否为平衡二叉树
     *
     * @param root
     * @return
     */
    public boolean IsBalanced_Solution(TreeNode root) {
        height(root);
        return isBalanced;
    }

    private int height(TreeNode root) {
        if (root == null || !isBalanced) {
            return 0;
        }
        int left = height(root.left);
        int right = height(root.right);
        if (Math.abs(left - right) > 1) {
            isBalanced = false;
            return 0;
        }
        return 1 + Math.max(left, right);
    }

    public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
        int n = array.length;
        HashSet<Integer> sets = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (sets.contains(array[i])) {
                sets.remove(array[i]);
            } else {
                sets.add(array[i]);
            }
        }
        Iterator<Integer> iterator = sets.iterator();
        if (sets.size() == 2) {
            num1[0] = iterator.next();
            num2[0] = iterator.next();
        }
    }

    /**
     * 剑指 Offer 63. 股票的最大利润
     * 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
     * <p>
     * <p>
     * <p>
     * 示例 1:
     * <p>
     * 输入: [7,1,5,3,6,4]
     * 输出: 5
     * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     * 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
     * 示例 2:
     * <p>
     * 输入: [7,6,4,3,1]
     * 输出: 0
     * 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE;
        int profit = 0;
        for (int price : prices) {
            cost = Math.min(price, cost);
            profit = Math.max(profit, price - cost);//dp[i] = max(dp[i-1],price-cost)
        }
        return profit;
    }

    /**
     * 66. 构建乘积数组
     * 题目描述
     * 给定一个数组 A[0, 1,..., n-1]，请构建一个数组 B[0, 1,..., n-1]，
     * 其中 B 中的元素 B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。要求不能使用除法。
     *
     * @param A
     * @return
     */
    public int[] multiply(int[] A) {
        int n = A.length;
        int[] b = new int[n];
        for (int i = 0, factor = 1; i < n; factor *= A[i], i++) {
            b[i] = factor;
        }

        for (int i = n - 1, factor = 1; i >= 0; factor *= A[i], i--) {
            b[i] *= factor;
        }
        return b;
    }

    /**
     * 67.字符串转成整数
     * 题目描述
     * 将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。
     * 数值为0或者字符串不是一个合法的数值则返回0
     * 输入描述:
     * 输入一个字符串,包括数字字母符号,可以为空
     * 输出描述:
     * 如果是合法的数值表达则返回该数字，否则返回0
     * 示例1
     * 输入
     * 复制
     * +2147483647
     * 1a33
     * 输出
     * 复制
     * 2147483647
     * 0
     *
     * @param str
     * @return
     */
    public int StrToInt(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char first = str.charAt(0);
        boolean isNegative = first == '-';
        int ans = 0;
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            if (i == 0 && (c == '+' || c == '-')) {
                continue;
            }
            if (c < '0' || c > '9') {
                return 0;
            }
            ans = 10 * ans + (c - '0');
        }
        return isNegative ? -ans : ans;
    }


    public int yuesefu(int n, int m) {

        LinkedList<Integer> queue = new LinkedList<>();
        if (n < 1) {
            return -1;
        }
        for (int i = 0; i < n; i++) {
            queue.add(i);
        }
        int i = 0;
        int ans = -1;
        while (queue.size() > 0) {
            ans = queue.poll();
            if (i < m) {
                queue.add(ans);
                i++;
            } else {
                i = 0;
            }
        }
        return ans;
    }
}

